package middle;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import util.PrintUtils;

public class Solution_56 {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (e1, e2) -> e1[0] - e2[0]);
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int[] interval : intervals) {
            max = Math.max(max, interval[1]);
            min = Math.min(min, interval[0]);
        }
        int[] flags = new int[max - min + 2];
        Arrays.fill(flags, -1);
        for (int[] interval : intervals) {
            int now = flags[interval[0] - min];
            now = now == -1 ? interval[0] : now;
            for (int i = interval[0]; i <= interval[1]; i++) {
                flags[i - min] = now;
            }
        }
        List<int[]> list = new ArrayList<>();
        int pre = -1;
        for (int i = 0; i < flags.length; i++) {
            if (flags[i] != pre) {
                if (pre != -1) {
                    list.add(new int[]{pre, i + min - 1});
                }
                pre = flags[i];
            }
        }
        return list.toArray(new int[0][]);
    }

    public static void main(String[] args) {
        Solution_56 model = new Solution_56();
//        int[][] merge = model.merge(new int[][]{{1,3},{2,6},{8,10},{15,18}});
//        int[][] merge = model.merge(new int[][]{{1,4},{5, 6}});
        int[][] merge = model.merge(new int[][]{{1,4},{0, 1}});
        for (int[] ints : merge) {
            PrintUtils.arrayInt(ints);
        }
    }
}
